Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Теорія алгоритмів і структури даних

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКНІ
Факультет:
КН
Кафедра:
Кафедра САПР

Інформація про роботу

Рік:
2010
Тип роботи:
Лабораторна робота
Предмет:
Алгоритмізація і програмування
Варіант:
10

Частина тексту файла

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра САПР / Звіт до лабораторної роботи № 10 на тему: Теорія алгоритмів і структури даних ЛЬВІВ – 2010 1. МЕТА РОБОТИ Метою роботи є вивчення алгоритмів сортування. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Сортуванням називають впорядковування по ключах (тобто за якою-небудь ознакою) елементів деякої структури даних на якій визначено відношення порядку. У залежності від того, чи знаходяться елементи структур даних у внутрішній (оперативній) пам’яті або у зовнішній пам’яті (на зовнішніх пристроях), розрізняють внутрішнє та зовнішнє сортування. Нехай існують послідовність a0, a1... an і функція порівняння, яка на будь-яких двох елементах послідовності приймає одне з трьох значень: менше, більше або дорівнює. Задача сортування полягає у перестановці елементів послідовності так,щоб виконувалася умова: ai <= ai+1, для всіх i від 0 до n. Можлива ситуація, коли елементи складаються з декількох полів (рис.4): struct element { field x; field y; } Якщо значення функції порівняння залежить тільки від поля x, то x називають ключем, по якому проводиться сортування. На практиці, в якості x часто виступає число, а поле у зберігає будь-які дані, жодним чином не впливаючи на роботу алгоритму. Мабуть, жодна інша проблема не породила такої кількості найрізноманітніших рішень, як задача сортування. Чи існує певний "універсальний, найкращий алгоритм"? Маючи приблизні характеристики вхідних даних, можна підібрати метод, який працює оптимальним чином. Для того, щоб обґрунтовано зробити такий вибір, розглянемо параметри, по яких проводититься оцінка алгоритмів. 1. Час сортування - основний параметр, що характеризує швидкодію алгоритму. 2. Пам’ять - ряд алгоритмів вимагає виділення додаткової пам’яті під тимчасове зберігання даних. При оцінці пам’яті, що використовується, не враховується місце, яке займає початковий масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми. 3. Стійкість - стійке сортування не міняє взаємного розташування рівних елементів. Така властивість може бути дуже корисною, якщо вони складаються з декількох полів, як на рис. 5, а сортування відбувається по одному з них, наприклад, по x. Рис.5 Приклад стійкого і нестійкого сортування Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" залишилося початковим: елемент з полем "a", потім - з "b", потім - з "c". Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a", "b", "c" змінилося. 4. Природність поведінки - ефективність методу при обробці вже відсортованих, або частково відсортованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще. Швидке сортування Алгоритм "швидкого сортування" був розроблений більше 40 років тому, і є найбільш широко вживаним і одним з найефективніших алгоритмів сортування. Метод заснований на підході "поділяй-і-владарюй". Загальна схема алгоритму наступна: 1. з масиву вибирається деякий опорний елемент а[i]; 2. запускається процедура розділення масиву, яка переміщає всі ключі, які менше-рівні а[i], ліворуч від нього, а всі ключі, більші, або дорівнюють а[i] – вправо; 3. тепер масив складається з двох підмножин, причому ліва менша, або дорівнює правій; 4. для обох підмасивів: якщо у підмасиві більше двох елементів, рекурсивно запускаємо для нього ту саму процедуру. У кінці роботи отримуємо повністю відсортовану послідовність. Розглянемо алгоритм детальніше. 1.7.1. Розділення масиву На вході масив а[0]...а[N] і опорний елемент p, по якому проводитиметься розділення. 1. Введемо два покажчики: i і j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності. 2. Рухатимемо покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i]>= p. Потім аналогічним чином почнемо рухати покажчик j від кінця масиву до початку, поки не буде знайдений а[j]<= p. 3. Далі, якщо i <= j, мі...
Антиботан аватар за замовчуванням

05.01.2013 15:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини